// 局部最优解 犀利 
// 动态规划 最优子结构 局部是和全局一致的 状态转移方程 dp[i] 
// 贪心 O(n) 时间复杂度
// 贪心是在每个决策点都选择在当前看起来最优的选择 ，不会去积累之前的最值
// 贪心
function maxProfit(price) {
    let low = Infinity // 无限大
    let result = 0
    // 暴力 O (n^2)
    for (let i = 0; i < price.length; i++) {
        low = Math.min(low, price[i])
        result = Math.max(result, price[i]-low)
    }
    return result

}

// dp 动态规划五部曲
// 贪心的每一步都选择最低价， 计算最大利润， dp 更关注之前的计算 
// dp[] 意义
// 初始化
// 状态转移方程
// 迭代
// 最值
function maxProfit(prices) {
    let n = prices.length
    if (n == 0) return 0
    // 当天的最值 第一天的最大利润
    let dp = new Array(n).fill(0)
    // 初始化 最低是0 没卖的机会
    let minPrice = prices[0]
    for (let i = 1; i < n; i++) {
        // 观测出来 公式 递归
        dp[i] = Math.max(dp[i-1], prices[i]-minPrice)
        minPrice = Math.min(dp[i-1], prices[i])
    }
    return dp[n-1]
}